package cn.zeronineten;

import java.util.ArrayList;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2020/9/10

*/
public class Solution {
    int max = 0;
    public static void main(String[] args) {
        //[[-1],[2,3],[1,-1,-3]]
        Solution s = new Solution();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> a = new ArrayList<>();
        a.add(-1);
        res.add(a);

        ArrayList<Integer> b = new ArrayList<>();
        b.add(2);b.add(3);
        res.add(b);

        ArrayList<Integer> c = new ArrayList<>();
        c.add(1);c.add(-1);c.add(-3);
        res.add(c);

        System.out.println(s.minimumTotal(res));

    }
    public int maxPathSum (TreeNode root) {
        // write code here
        if (root == null){
            return 0;
        }
        getMax(root);
        return max;
    }

    public int getMax(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftMax = Math.max(0,maxPathSum(root.left));
        int rightMax = Math.max(0,maxPathSum(root.right));

        max = Math.max(max,leftMax + rightMax + root.val);
        return Math.max(0,root.val + Math.max(leftMax,rightMax));
    }

    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far.
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }

    public int maxProfit2 (int[] prices) {
        // write code here
        int sum = 0;
        for (int i = 0; i < prices.length-1; i++) {
            if (prices[i+1] > prices[i]){
                sum += prices[i+1]-prices[i];
            }
        }
        return sum;
    }

    public int maxProfit3 (int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int max=0;
        int min=prices[0];
        for(int i=0;i<prices.length;i++){
            min = Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }

    //动态规划算法：动态规划算法与分治法类似，都是通过将问题划分为子问题，然后分别解决子问题，不同的是分治法的子问题是互相独立的
    //而动态规划算法划分的子问题是之间相互影响的。
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
       if (triangle.size() < 1) return 0;
       int min[] = new int[triangle.size()];
        for (int i = 0; i < triangle.size(); i++) {
            min[i] = triangle.get(triangle.size()-1).get(i);
        }

        for (int i = triangle.size()-2; i >= 0 ; i--) {
            for (int j = 0; j <= i; j++) {
                min[j] = Math.min(min[j] + triangle.get(i).get(j),min[j+1] + triangle.get(i).get(j));
            }
        }
        return min[0];
    }
}




class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
 }